"""
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"
示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:

所有输入只包含小写字母 a-z 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

击败97%
"""
from typing import List

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nodes = {}


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        nodes = self.nodes
        for s in word:
            if s in nodes:
                nodes = nodes[s]
            else:
                new_dict = {}
                nodes[s] = new_dict
                nodes = new_dict
        else:
            nodes["end"] = True

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        t = Trie()
        for s in strs:
            if not s:
                return ""
            t.insert(s)
        print(t.nodes)
        nodes = t.nodes
        ans = []
        while len(nodes) == 1:
            tmp = list(nodes.keys())[0]
            nodes = nodes[tmp]
            ans.append(tmp)
            if "end" in nodes:
                break
        return "".join(ans)

def test():
    assert Solution().longestCommonPrefix(["flower","flow","flight"]) == "fl"
    assert Solution().longestCommonPrefix(["aa", "a"]) == "a"
    assert Solution().longestCommonPrefix(["a"]) == "a"

if __name__ == "__main__":
    print(Solution().longestCommonPrefix(["a"]))